#include <algorithm>
#include <utility>
#include <vector>

class Solution {
 public:
  std::vector<std::vector<int>> combinationSum2(std::vector<int> &candidates,
                                                int target)
  {
    std::sort(candidates.begin(), candidates.end());

    for (int i : candidates)
    {
      if (vec_nums_.empty() || vec_nums_.back().first != i)
      {
        vec_nums_.emplace_back(i, 1);
      } else
      {
        ++vec_nums_.back().second;
      }
    }

    dfs(0, target);

    return ret_;
  }

  void dfs(int pos, int remain)
  {
    if (remain == 0)
    {
      ret_.push_back(queue_);
      return;
    }

    if (pos == vec_nums_.size() || vec_nums_[pos].first > remain) { return; }

    dfs(pos + 1, remain);

    int most = std::min(vec_nums_[pos].second, remain / vec_nums_[pos].first);

    for (int i = 1; i <= most; ++i)
    {
      queue_.push_back(vec_nums_[pos].first);
      dfs(pos + 1, remain - i * vec_nums_[pos].first);
    }

    for (int i = 0; i != most; ++i) { queue_.pop_back(); }
  }

 private:
  std::vector<int> queue_;
  std::vector<std::vector<int>> ret_;
  std::vector<std::pair<int, int>> vec_nums_;
};
